// Time:  O(n)
// Space: O(1)
#include <vector>
#include <algorithm>
#include <cassert>
class Solution {
public:
    double averageWaitingTime(std::vector<std::vector<int>>& customers) {
        double avai = 0, wait = 0;
        for (const auto& c : customers) {
            avai = std::max(avai, double(c[0])) + c[1];
            wait += avai - c[0];
        }
        return wait / customers.size();
    }
};

int main() {
    std::vector<std::vector<int>> customers = {{1, 2}, {2, 5}, {4, 3}};
    Solution sol;
    assert(sol.averageWaitingTime(customers) == 5.0);
    return 0;
}